package everyday;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-07-11-12:29
 * @Description: 1.0
 */
public class T1911 {
    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;
        long[][] dp = new long[n][2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dp(nums, dp, 0, 0);
    }

    public long dp(int[] nums, long[][] dp, int a, int b) {
        if (dp[a][b] != -1) return dp[a][b];
        long res = 0;
        if (b == 0) {
            res += nums[a];
        } else {
            res -= nums[a];
        }
        if (a == nums.length - 1) return Math.max(res, 0);
        res = Math.max(res + dp(nums, dp, a + 1, 1 - b), dp(nums, dp, a + 1, b));
        dp[a][b] = res;
        return res;
    }
}
